package main.leetcode.clockin.June;

/**
 * 面试题 16.18. 模式匹配
 *
 * <p>你有两个字符串，即pattern和value。
 * pattern字符串由字母"a"和"b"组成，用于描述字符串中的模式。例如，字符串"catcatgocatgo"匹配模式"aabab"（其中"cat"是"a"，"go"是"b"），该字符串也匹配像"a"、"ab"和"b"这样的模式。但需注意"a"和"b"不能同时表示相同的字符串。编写一个方法判断value字符串是否匹配pattern字符串。
 *
 * <p>示例 1：输入： pattern = "abba", value = "dogcatcatdog" 输出： true
 *
 * <p>示例 2：输入： pattern = "abba", value = "dogcatcatfish" 输出： false
 *
 * <p>示例 3：输入： pattern = "aaaa", value = "dogcatcatdog" 输出： false
 *
 * <p>示例 4：输入： pattern = "abba", value = "dogdogdogdog" 输出： true 解释： "a"="dogdog",b=""，反之也符合规则
 *
 * <p>提示：0 <= len(pattern) <= 1000 0 <= len(value) <= 1000 你可以假设pattern只包含字母"a"和"b"，value仅包含小写字母。
 */
public class day22 {
    public static void main(String[] args) {
        //        System.out.println(new day22().patternMatching("abba", "dogcatcatdog"));
        //        System.out.println(new day22().patternMatching("abba", "dogcatcatfish"));
        System.out.println(new day22().patternMatching("aaaa", "dogcatcatdog"));
        System.out.println(new day22().patternMatching("abba", "dogdogdogdog"));
    }

    public boolean patternMatching(String pattern, String value) {
        int m = pattern.length(), n = value.length();
        // 1 求a的个数，b的个数
        int cntA = 0, cntB = 0;
        for (int i = 0; i < m; ++i) {
            if (pattern.charAt(i) == 'a') {
                ++cntA;
            } else {
                ++cntB;
            }
        }
        // 1.2 约定 a > b
        if (cntA < cntB) {
            cntA = cntA + cntB - (cntB = cntA);
            char[] chars = pattern.toCharArray();
            for (int i = 0; i < m; ++i) {
                chars[i] = chars[i] == 'a' ? 'b' : 'a';
            }
            pattern = new String(chars);
        }
        // 1.3 特殊判断
        if (value.isEmpty()) {
            return cntB == 0;
        }
        if (pattern.isEmpty()) {
            return false;
        }
        // 1.4 计算a对应字符串长度的上限 n/a
        int maxLenA = (int) Math.floor((double) n / cntA);
        // 1.5 计算a、b首次出现的下标
        int firstA = pattern.indexOf('a'), firstB = pattern.indexOf('b');
        // 2 枚举a、b的长度
        int lenA, lenB;
        String a, b;
        for (int i = 0; i <= maxLenA; ++i) {
            lenA = i;
            lenB = cntB == 0 ? 0 : (n - cntA * lenA) / cntB;
            // 2.1 根据长度和首次出现下标寻找对应的字符串
            firstB = cntB == 0 ? 0 : firstB;
            a = value.substring(lenB * firstA, lenB * firstA + lenA);
            b = value.substring(lenA * firstB, lenA * firstB + lenB);
            // 2.2 a、b不相等
            if (a.equals(b)) {
                continue;
            }
            // 2.3 比较该情况是否满足
            char[] chars = pattern.toCharArray();
            StringBuilder tmp = new StringBuilder();
            for (int j = 0; j < m; ++j) {
                tmp.append(chars[j] == 'a' ? a : b);
            }
            if (tmp.toString().equals(value)) {
                return true;
            }
        }
        return false;
    }
}
